|
In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move. Rook's graphs are highly symmetric perfect graphs; they may be characterized in terms of the number of triangles each edge belongs to and by the existence of a 4-cycle connecting each nonadjacent pair of vertices. ==Definitions== An ''n'' × ''m'' rook's graph represents the moves of a rook on an ''n'' × ''m'' chessboard. Its vertices may be given coordinates (''x'',''y''), where 1 ≤ ''x'' ≤ ''n'' and 1 ≤ ''y'' ≤ ''m''. Two vertices (''x''1,''y''1) and (''x''2,''y''2) are adjacent if and only if either ''x''1 = ''x''2 or ''y''1 = ''y''2; that is, if they belong to the same rank or the same file of the chessboard. For an ''n'' × ''m'' rook's graph the total number of vertices is simply ''nm''. For an ''n'' × ''n'' rook's graph the total number of vertices is simply and the total number of edges is ; in this case the graph is also known as a two-dimensional Hamming graph or a Latin square graph. The rook's graph for an ''n'' × ''m'' chessboard may also be defined as the Cartesian product of two complete graphs ''K''''n'' ''K''''m''. The complement graph of a 2 × ''n'' rook's graph is a crown graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rook's graph」の詳細全文を読む スポンサード リンク
|